/**
 * @Author：徐志荣
 * @Date：2023/9/8 上午 10:04
 */
public class Day0908 {
    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println("76. 最小覆盖子串 " + minWindow(s,t));
        int[] nums = {-1,0,3,5,9,12};
        int target = 9;
        System.out.println("704. 二分查找 : "+search(nums,target));

    }
    public static String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();

        int[] hash1 = new int[128]; //统计字符串t中字符的频次
        int kinds = 0; //字符串 t中，有多少种字符？
        for(char ch : t){
            if(hash1[ch] == 0){
                kinds++; //如果 这个字符是第一次进来的话，kinds++
            }
            hash1[ch]++; // 标记这个值 ++
        }
        int[] hash2 = new int[128]; // 统计窗口中字符的频次
        int minlen = Integer.MAX_VALUE,begin = -1;
        for(int left = 0,right = 0,count = 0;right<s.length;right++){
            char in = s[right];
            //进窗口
            hash2[in]++;
            if(hash2[in] == hash1[in]){
                count++; // 说明这个是个有效字符
            }
            while(kinds == count){ //判断
                //更新结果
                if(right - left + 1 <minlen){
                    begin = left;
                    minlen = right-left+1;
                }
                //出窗口
                char out = s[left];
                if(hash2[out] == hash1[out]){ // 如果是个有效字符出去了
                    count--;
                }
                hash2[out]--;
                left++;
            }
        }

        if(begin == -1){
            return new String();
        }else{
            return ss.substring(begin,begin+minlen);
        }
    }

    public static int search(int[] nums, int target) {
        int left = 0,right = nums.length-1;
        while(left<=right){
            int mid = left + (right-left) / 2; // 求中间点，不会溢出
            if(nums[mid]<target){
                left = mid+1;
            }else if(nums[mid] > target){
                right = mid-1;
            }else{
                return mid;
            }
        }
        return -1;
    }

}
